package main

import (
	"errors"
	"fmt"
)

func main() {
	//m := make(map[int]int, 10)
	//for i := 1; i <= 10; i++ {
	//	m[i] = i
	//}
	//
	//for k, v := range m {
	//	go func() {
	//		fmt.Println("k ->", k, "v ->", v)
	//	}()
	//}
	//time.Sleep(10 * time.Second)
)

func main() {
	fmt.Println(binarySearch([]int{1,2,4,4,4,4,4,6,9,10}, 4))
	fmt.Println(binarySearchLeftBound([]int{1,2,4,4,4,4,4,6,9,10}, 4))
	fmt.Println(binarySearchRightBound([]int{1,2,4,4,4,4,4,6,9,10}, 4))
	linkedStackDemo()
}

func minPathSum(grid [][]int) int {
	result := make([]int, len(grid[0]))
	row := 1
	for result[0], row = grid[0][0], 1; row < len(grid[0]); row++ {
		result[row] = grid[0][row] + result[row-1]
	}
	for col := 1; col < len(grid); col++ {
		for result[0], row = result[0]+grid[col][0], 1; row < len(grid[0]); row++ {
			if result[row-1] < result[row] {
				result[row] = result[row-1] + grid[col][row]
			} else {
				result[row] = result[row] + grid[col][row]
			}
		}
	}
	return result[len(result)-1]
}

type stack struct {
	arrs []int
}

func (st *stack) push(val int) {
	st.arrs = append(st.arrs, val)
}

func (st *stack) pop() int {
	if len(st.arrs) == 0 {
		panic(errors.New("size 0"))
	}
	res := st.arrs[len(st.arrs)-1]
	st.arrs = st.arrs[:len(st.arrs)-1]
	return res
}

func (st *stack) isEmpty() bool {
	return len(st.arrs) == 0
}

func reverseStack() {
	st := &stack{arrs: make([]int, 0)}
	st.push(1)
	st.push(2)
	st.push(3)
	st.push(4)
	st.push(5)

}

func moveBottomToTop(s *stack) {
	if
}
func binarySearch(nums []int, target int) int {
	left := 0
	right := len(nums) - 1
	for left <= right {
		mid := left + (right - left) / 2
		if nums[mid] == target{
			return mid
		} else if nums[mid] < target {
			left = mid + 1
		} else {
			right = mid - 1
		}
	}
	return -1
}

func binarySearchLeftBound(nums []int, target int) int {
	left := 0
	right := len(nums) - 1
	for left < right {
		mid := left + (right - left) / 2
		if nums[mid] == target{
			right = mid
		} else if nums[mid] < target {
			left = mid + 1
		} else {
			right = mid - 1
		}
	}
	return left
}

func binarySearchRightBound(nums []int, target int) int {
	left := 0
	right := len(nums) - 1
	for left < right {
		mid := left + (right - left) / 2
		if nums[mid] == target{
			left = mid
		} else if nums[mid] < target {
			left = mid + 1
		} else {
			right = mid - 1
		}
	}
	return right
}

type ListNode struct {
	Val int
	Next *ListNode
}

type LinkedStack struct {
	head *ListNode
}

func NewStack()*LinkedStack{
	return &LinkedStack{
		head: &ListNode{},
	}
}

func (ls *LinkedStack) IsEmpty() bool {
	return ls.head.Next == nil
}

func (ls *LinkedStack)Push(e int) {
	newNode := &ListNode{
		Val:e,
		Next:ls.head.Next,
	}
	ls.head.Next = newNode
}

func (ls *LinkedStack)Pop() int {
	tmp := ls.head.Next
	if tmp != nil {
		ls.head.Next = tmp.Next
		return tmp.Val
	}
	panic(errors.New("stack is empty, no more value"))
}

func (ls *LinkedStack)Top() int {
	if ls.head.Next != nil {
		return ls.head.Next.Val
	}
	panic(errors.New("stack is empty, no more value"))
}

func linkedStackDemo(){
	defer func(){
		if err := recover();err!=nil{
			fmt.Println(err)
		}
	}()
	stack := NewStack()
	stack.Push(5)
	stack.Push(4)
	stack.Push(3)
	stack.Push(2)
	stack.Push(1)
	fmt.Println("top stack: ", stack.Top())
	stack.Pop()
	fmt.Println("top stack: ", stack.Top())
	stack.Pop()
	fmt.Println("top stack: ", stack.Top())
	stack.Pop()
	fmt.Println("top stack: ", stack.Top())
	stack.Pop()
	fmt.Println("top stack: ", stack.Top())
	stack.Pop()
	fmt.Println("top stack: ", stack.Top())
}
